'''
   概念：
        1.堆（heap）是一种树形数据结构，可以保证父节点比子节点打大或者小。当根节点保存堆里的最大值时为大根堆；反之为小根堆。
        2.二叉堆(Binary Heap)是最简单常用的堆，一颗符合堆的性质的完全二叉树。在进行二叉堆的操作时我们要注意堆结构和堆顺序的保持。
        logn就是从堆这里面出来的。
'''

# 实现一个二叉堆的构造函数，小根堆
class BinHeap:
    def __init__(self):
        self.heaplist = [0]
        self.currentSize = 0

    # 插入元素
    def insert(self,k):
        self.heaplist.append(k)
        self.currentSize = self.currentSize + 1
        self.percUp(self.currentSize)   # 维护堆顺序

    # 删除元素,一般都是删除顶部元素
    def delMin(self):
        retval = self.heaplist[1]   # 根元素
        self.heaplist[1] = self.heaplist[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heaplist.pop() # 删除最后一个元素
        self.percDown(1)    # 维持堆顺序
        return retval

    # 输入一个列表，将列表转化成堆结构和堆顺序，只需要从最后叶子结点的父节点开始检查直到检查到根节点。
    def buildHeap(self,alist):
        i = len(alist)//2   # 第一个父节点
        self.currentSize = len(alist)
        self.heaplist = [0] + alist[:]
        while i > 0:
            self.percDown(i)
            i = i - 1

    # 删除元素后的堆顺序维持，就是根节点通过排序移到合适位置。
    # 思路：跟节点和左右节点比较(前提是有节点，即i*2<size)。左右节点先比较，我们取那个小一点的节点，然后根节点和这个节点交换位置
    # 输入某一个节点位置，从该节点向下实现排序满足该位置的堆顺序结构
    def percDown(self,i):
        while (i * 2) <= self.currentSize:  # 说明有子节点
            mc = self.minChild(i)   # 最小的子节点
            if self.heaplist[i] > self.heaplist[mc]:
                temp = self.heaplist[i]
                self.heaplist[i] = self.heaplist[mc]
                self.heaplist[mc] = temp
            i = mc

    def minChild(self,i):
        if i * 2 + 1 > self.currentSize:
            return i * 2
        else:
            if self.heaplist[i * 2] < self.heaplist[i * 2 + 1]:
                return i * 2
            else:
                return i * 2 + 1

    # 插入元素后维持堆顺序
    def percUp(self,i):
        while i//2 > 0: # 直到根节点
            if self.heaplist[i] < self.heaplist[i//2]:
                tmp = self.heaplist[i//2]
                self.heaplist[i//2] = self.heaplist[i]
                self.heaplist[i] = tmp
            i = i//2

# 根节点数字最大,大根堆
class BinHeapMax:
    def __init__(self):
        self.heaplist = [0]
        self.currentSize = 0

    def percUp(self,i):
        while i//2 > 0:
            if self.heaplist[i] > self.heaplist[i//2]:
                temp = self.heaplist[i//2]
                self.heaplist[i//2] = self.heaplist[i]
                self.heaplist[i] = temp
            i = i//2

    def insert(self,k):
        self.heaplist.append(k)
        self.currentSize = self.currentSize + 1
        self.percUp(self.currentSize)

    def percDown(self,i):
        while (i * 2) < self.currentSize:   # 要获得子节点较大的那一个
            mc = self.maxChild(i)
            if self.heaplist[i] < self.heaplist[mc]:    # 根节点小
                temp = self.heaplist[i]
                self.heaplist[i] = self.heaplist[mc]
                self.heaplist[mc] = temp
            i = mc

    def maxChild(self,i):
        if (i * 2 + 1) > self.currentSize:
            return  i * 2
        else:
            if self.heaplist[i*2] > self.heaplist[i*2+1]:
                return i*2
            else:
                return i*2+1

    def delMax(self):
        retval = self.heaplist[1]
        self.heaplist[1] = self.heaplist[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heaplist.pop()
        self.percDown(1)
        return retval

    def buildHeap(self,alist):
        i = len(alist)//2
        self.currentSize = len(alist)
        self.heaplist = [0] + alist[:]
        while i > 0:
            self.percDown(i)
            i = i - 1

bh = BinHeap()
bh.buildHeap([9,5,6,2,3])
alist = bh.heaplist
print(alist)
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
b = BinHeapMax()
b.buildHeap([9,5,6,2,3])
alist = b.heaplist
print(alist)
print(b.delMax())
print(b.delMax())
print(b.delMax())
print(b.delMax())
print(b.delMax())